Exercise: Graphs

Find if an AdjacencyMatrix has a universal sink.

We'll cover the following

Task#

A universal sink in a graph GG is a vertex that is the target of n−1n − 1 edges and the source of no edges. Design and implement an algorithm that tests if a graph GG, represented as an AdjacencyMatrix, has a universal sink. Your algorithm should run in O(n)O(n) time.

Sample input

The sample input will be as follows:

(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)

Expected output

The expected output will be as follows:

Universal Sink not found.
Vertex 4 is a Universal Sink in graph.

Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.

Good luck!

svg viewer

Note: You must implement the method find_uni_sink_on() in the below code starting at line 52.

main.py
utils.py
Implementation to find universal sink in a graph

Discussion on Graphs

Solution: Graphs